#!/usr/bin/env python


DECIMAL_TO_ROMAN = [
    {0: '', 1: 'I', 2: 'II', 3: 'III', 4: 'IV', 5: 'V', 6: 'VI', 7: 'VII', 8: 'VIII', 9: 'IX',},   # Conversion for the ones place.
    {0: '', 1: 'X', 2: 'XX', 3: 'XXX', 4: 'XL', 5: 'L', 6: 'LX', 7: 'LXX', 8: 'LXXX', 9: 'XC',},   # Conversion for the tens place.
    {0: '', 1: 'C', 2: 'CC', 3: 'CCC', 4: 'CD', 5: 'D', 6: 'DC', 7: 'DCC', 8: 'DCCC', 9: 'CM',},   # Conversion for the hundreds place.
                                                                                                   # Romans couldn't count higher than 999.
]


def _decimal_to_coeffs(num):
    return [int(c) for c in str(num)]


def _coeffs_to_roman(coeffs):

    # Romans couldn't count higher than 999.
    assert len(coeffs) <= 3

    coeffs.reverse()
    romans = []
    for pow_of_10 in range(len(coeffs)):
        coeff = coeffs[pow_of_10]
        roman_dict = DECIMAL_TO_ROMAN[pow_of_10]
        roman = roman_dict[coeff]
        romans.insert(0, roman)
    roman = ''.join(romans)
    return roman


def decimal_to_roman(num):
    coeffs = _decimal_to_coeffs(num)
    roman = _coeffs_to_roman(coeffs)
    return roman


def roman_to_decimal(roman):
    """Convert a Roman numeral to a decimal number.

    Example usage:
        >>> roman_to_decimal('i')
        1
        >>> roman_to_decimal('ii')
        2
        >>> roman_to_decimal('iii')
        3
    """
    roman = roman.upper()
    decimal = 0

    for pow_of_10 in range(3):
        roman_dict = DECIMAL_TO_ROMAN[pow_of_10]
        roman_list = roman_dict.items()
        roman_list = sorted(roman_list, key=lambda item: len(item[1]),
                            reverse=True)

        for decimal_digit, roman_digit in roman_list:
            if decimal_digit and roman.endswith(roman_digit):
                decimal += decimal_digit * 10 ** pow_of_10
                roman = roman[:-len(roman_digit)]
                break

    if roman:
        # We just went through our entire mapping of decimal digits to Roman
        # numerals, yet we still have some letters left in our string.
        # Therefore, our string must not be a valid Roman numeral.
        raise ValueError

    return decimal


def is_roman(string):
    """Determine whether or not a string is a valid Roman numeral.

    Example usage:
        >>> is_roman('i')
        True
        >>> is_roman('ii')
        True
        >>> is_roman('iii')
        True

        >>> is_roman('drew')
        False
        >>> is_roman('raj')
        False
    """
    try:
        roman_to_decimal(string)
    except ValueError:
        return False
    else:
        return True


def main():
    import doctest
    doctest.testmod(verbose=True)


if __name__ == '__main__':
    main()
